Theory of Computation
Q171.
Consider the following two statements : S1: {0^{2n}|n\geq 1|} is a regular language S2 : {0^{m}1^{n}0^{m+n}|m\geq 1 and n\geq 1|} is a regular language Which of the following statements is correct?Q172.
Consider the following two statements about regular languages: S1: Every infinite regular language contains an undecidable language as a subset. S2: Every finite language is regular. Which one of the following choices is correct?Q173.
Let L be a regular language. Consider the constructions on L below: I. \text{repeat} (L) = \{ww \mid w \in L\} II. \text{prefix} (L) = \{u \mid \exists v : uv \in L\} III. \text{suffix} (L) = \{v \mid \exists u: uv \in L\} IV. \text{half} (L) = \{u \mid \exists v: | v | = | u | \text{ and } uv \in L\}Which of the constructions could lead to a non-regular language?Q174.
L1 is a recursively enumerable language over \Sigma. An algorithm A effectively enumerates its words as w1, w2, w3, ... define another language L2 over \SigmaU{#} as {wi # wj : wi, wj \in L1, i \lt j}. Here # is a new symbol. Consider the following assertions. S1 : L1 is recursive implies L2 is recursive S2 : L2 is recursive implies L1 is recursive Which of the following statements is true ?Q175.
Let \Sigma=\left\{0,1\right\}, L = \Sigma^* \text{ and } R=\left\{0^n1^n \mid n \gt 0\right\} then the languages L \cup R and R are respectivelyQ176.
If s is a string over (0+1)*, then let n_0 (s) denote the number of 0's in s and n_1 (s) the number of 1's in s. Which one of the following languages is not regular?Q177.
Consider the following languages : L1 = {ww| w\in {a,b}*} L2 = {ww^{R}| w\in {a,b} *, w^{R} is the reverse of w} L3 = {0^{2i}| i is an integer} L4 ={0^{{i}^{2}} | i is an integer} Which of the languages are regular ?Q178.
Choose the correct alternatives (more than one may be correct) and write the corresponding letters only:Which of the following is the strongest correct statement about a finite language over some finite alphabet \Sigma?Q179.
Language L1 is defined by the grammar: S_{1}\rightarrow aS_{1}b|\varepsilon Language L2 is defined by the grammar: S_{2}\rightarrow abS_{2}|\varepsilon Consider the following statements: P: L1 is regular Q: L2 is regular Which one of the following is TRUE?